/* A* algorithm to solve the 8 puzzle. The heuristic value used for a state is
 * the number of elements in the wrong place + number of steps taken to reach
 * the state. At every iteration the top element i.e. the one with minimum
 * heuristic value is popped. */
#include <iostream>
#include <queue>
#include <string.h>
#include <assert.h>

#define N 3

using namespace std;

void swap(int *x, int *y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}


/* View the cells as matrix to print and manipulate. View them as array to
 * compare and copy
 */
union Cells {
	int matrix[N][N];
	int linear[N * N];
};

enum direction {
	UP, DOWN, LEFT, RIGHT
};

class State {
	private:
		Cells c;
		int hamming;

	public:
		int steps;
		int heuristic;

		State(int steps, int array[]) : hamming(0), steps(steps),
						 heuristic(steps) {
			memcpy(c.linear, array, sizeof(c.linear));
			calc_hamming();
			heuristic += hamming;
		}

		void calc_hamming(void)
		{
			for (int i = 0; i < N * N; i++) {
				if (c.linear[i] && c.linear[i] != i+1)
					hamming++;
			}
		}

		bool operator == (const State & state)
		{
			return !(memcmp(c.linear, state.c.linear,
					 sizeof(c.linear)));
		}

		bool operator != (const State & state)
		{
			return memcmp(c.linear, state.c.linear,
				      sizeof(c.linear));
		}

		int get_0_pos(void)
		{
			for (int i = 0; i < N * N; i++) {
				if (!c.linear[i])
					return i;
			}

			/* Never reaches. Shut the compiler */
			return 0;
		}

		State* get_next_state(enum direction d)
		{
			int zero_pos = get_0_pos();
			int zero_i = zero_pos / N;
			int zero_j = zero_pos % N;

			Cells ncells;
			memcpy(ncells.linear, c.linear, sizeof(c.linear));

			switch (d) {
				case UP:
					/* Can't move up */
					if (zero_i == 0)
						return NULL;

					swap(&ncells.matrix[zero_i][zero_j],
					     &ncells.matrix[zero_i - 1][zero_j]);
					break;

				case DOWN:
					if (zero_i == N-1)
						return NULL;

					swap(&ncells.matrix[zero_i][zero_j],
					     &ncells.matrix[zero_i + 1][zero_j]);
					break;

				case LEFT:
					if (zero_j == 0)
						return NULL;

					swap(&ncells.matrix[zero_i][zero_j],
					     &ncells.matrix[zero_i][zero_j - 1]);
					break;

				case RIGHT:
					if (zero_j == N-1)
						return NULL;

					swap(&ncells.matrix[zero_i][zero_j],
					     &ncells.matrix[zero_i][zero_j + 1]);
					break;

				default:
					assert(0);

			}

			return new State(steps + 1, ncells.linear);
		}

		void print(void)
		{
			for (int i=0; i < N; i++) {
				for (int j=0; j < N; j++) {
					cout.width(4);
					cout << c.matrix[i][j];
				}
				cout << endl;
			}
			cout << endl;
		}
};


class State_comparison
{
	public:
		bool operator () (const State * lhs, const State * rhs)
		{
			return lhs->heuristic > rhs->heuristic;
		}
};

priority_queue < State *, vector < State * >, State_comparison > state_heap;

int initial[] = { 4, 1, 3, 7, 2, 5, 8, 0, 6};
int final[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };

State *initial_state = new State(0, initial);
State final_state(0, final);	/* The number does not matter here. We only
				   compare the cells */

int main(void)
{
	state_heap.push(initial_state);
	State *state = state_heap.top();

	State prev_state = *state;
	State cur_state = *state_heap.top();

	while (cur_state != final_state) {
		cur_state.print();

		delete(state_heap.top());
		state_heap.pop();

		State *new_state;

		new_state = cur_state.get_next_state(UP);
		if (new_state && (*new_state != prev_state))
			state_heap.push(new_state);
		else
			delete(new_state);

		new_state = cur_state.get_next_state(DOWN);
		if (new_state && (*new_state != prev_state))
			state_heap.push(new_state);
		else
			delete(new_state);

		new_state = cur_state.get_next_state(LEFT);
		if (new_state && (*new_state != prev_state))
			state_heap.push(new_state);
		else
			delete(new_state);

		new_state = cur_state.get_next_state(RIGHT);
		if (new_state && (*new_state != prev_state))
			state_heap.push(new_state);
		else
			delete(new_state);

		prev_state = cur_state;
		cur_state = *state_heap.top();
	}
	cur_state.print();

	while (!state_heap.empty()) {
		delete(state_heap.top());
		state_heap.pop();
	}

	return 0;
}
